package com.fyl.basic_algorithm.linkedList;

/**
 * 1) 单链表反转
 * 2) 链表中环的检测
 * 3) 两个有序的链表合并
 * 4) 删除链表倒数第n个结点
 * 5) 求链表的中间结点
 *
 * @author 冯永龙
 * @date 2021/3/13 16:34
 */
public class LinkedListAlgo {

    //单链表反转
    public static Node reverse(Node list) {
        Node pre = null;
        Node r = list;
        Node next = null;
        while (r != null) {
            next = r.next;
            r.next = pre;
            pre = r;
            r = next;
        }

        return pre;
    }

    //检测环
    public static boolean checkCircle(Node list) {
        if (list == null) return false;

        Node fast = list.next;
        Node slow = list;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) return true;
        }

        return false;
    }

    public static Node mergeSortedLists(Node la, Node lb) {
        if (la == null) return lb;
        if (lb == null) return la;

        Node head = null;
        Node p = la;
        Node q = lb;

        if (la.data < lb.data) {
            head = la;
        } else {
            head = lb;
        }

        while (p != null && q != null) {
            if (p.data < q.data) {
                head.next = p;
                p = p.next;
            } else {
                head.next = q;
                q = q.next;
            }
            head = head.next;
        }

        if (p != null) {
            head.next = p;
        }
        if (q != null) {
            head.next = q;
        }
        return head;

    }

    //删除倒数第K个节点
    public static Node deleteLastKth(Node list, int k) {
        Node fast = list;
        int i = 1;
        if (fast != null && i < k) {
            fast = fast.next;
        }

        Node slow = list;
        Node prev = null;

        while (fast.next != null) {
            fast = fast.next;
            prev = slow;
            slow = slow.next;
        }

        if (prev==null){
            list = list.next;
        }else {
            prev.next = prev.next.next;
        }

        return list;
    }

    //求中间节点
    public static Node findMiddleNode(Node list) {
        if (list == null) return null;

        Node fast = list;
        Node slow = list;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

        }

        return slow;
    }

    public static void printAll(Node list) {
        Node p = list;
        while (p != null) {
            System.out.println(p.data + " ");
            p = p.next;
        }
        System.out.println();
    }

    public static class Node {
        private int data;
        private Node next;

        public Node(int data, Node next) {
            this.data = data;
            this.next = next;
        }

        public int getData() {
            return data;
        }
    }
}
